package com.yunsom.testdemo.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.Stack;
import java.util.stream.Collectors;

public class DataStructurePractice {
    /*
    队列 Queue
    链表 Linked List
    数组 Array
    哈希表 Hash Table
    二叉树 Binary Tree
    堆 Heap
    并查集 Union Find
    字典树 Trie
     */
    public static void main(String[] args) {

        System.out.println("买卖股票最佳时机");
        System.out.println(getBiggestProfits(new int[]{7,1,5,3,6,4}));
        System.out.println(getBiggestProfits(new int[]{7,6,4,3,1}));

        System.out.println("求两数组交集");
        System.out.println(Arrays.toString(getTwoArrayIntersection(new int[]{1, 2, 2, 1}, new int[]{2, 2})));
        System.out.println(Arrays.toString(getTwoArrayIntersection(new int[]{4, 9, 5}, new int[]{9, 4, 9, 8, 4})));

        System.out.println("生成指定行数杨辉三角二维数组");
        System.out.println(generateYangHuiTriangle(3));

        System.out.println("寻找字符串第一个不重复的字符");
        System.out.println(findFirstUniqChar("leetcode"));
        System.out.println(findFirstUniqChar("loveleetcode"));
        System.out.println(findFirstUniqChar("aabb"));

        System.out.println("判断字符串A能不能由字符串B里面的字符构成");
        System.out.println(judgeStringCanBeConstructByOtherStringChar("a", "b"));
        System.out.println(judgeStringCanBeConstructByOtherStringChar("aa", "ab"));
        System.out.println(judgeStringCanBeConstructByOtherStringChar("aa", "aab"));

        System.out.println("矩阵置零");
        int[][] matrix1={
            {1,1,1},
            {1,0,1},
            {1,1,1}
        };
        System.out.println(Arrays.deepToString(getSetZeroMatrix(matrix1)));
        int[][] matrix2={
            {0,1,2,0},
            {3,4,5,2},
            {1,3,1,5}
        };
        System.out.println(Arrays.deepToString(getSetZeroMatrix(matrix2)));

        System.out.println("已知一个链表的头节点，判断链表中是否有环");
        ListNode listNode1 = new ListNode(1, new ListNode(2, new ListNode(3)));
        listNode1.show();
        System.out.println(judgeLinkedListNodeHaveLoop(listNode1));

        System.out.println("反转链表");
        ListNode listNode2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        reverseListNode1(listNode2).show();

        System.out.println("删除排序链表中的重复元素");
        ListNode listNode3 = new ListNode(1, new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(3)))));
        ListNode listNode4 = new ListNode(1, new ListNode(1, new ListNode(2)));
        System.out.println(deleteListNodeDuplicateElements(listNode3));
        listNode3.show();

        System.out.println("有效的括号");
        System.out.println(judgeValidBracket("()"));
        System.out.println(judgeValidBracket("()[]{}"));
        System.out.println(judgeValidBracket("(]"));
        System.out.println(judgeValidBracket("([)]"));
        System.out.println(judgeValidBracket("{[()]}"));

        System.out.println("用栈实现队列");
        MyQueue myQueue = new MyQueue();
        myQueue.push(1); // queue is: [1]
        myQueue.push(2); // queue is: [1,2]
        myQueue.push(3); // queue is: [1,2,3]
        myQueue.push(4); // queue is: [1,2,3,4] (leftmost is front of the queue)
        System.out.println(myQueue.pop()); // return 1, queue is [2,3,4]
        myQueue.push(5); // queue is: [2,3,4,5]
        System.out.println(myQueue.pop()); // return 2, queue is [3,4,5]
        System.out.println(myQueue.pop()); // return 3, queue is [4,5]
        System.out.println(myQueue.pop()); // return 4, queue is [5]
        System.out.println(myQueue.pop()); // return 5, queue is []
        myQueue.empty(); // return true

        TreeNode root = new TreeNode(
            3,
            new TreeNode(2, new TreeNode(0, null, null) , new TreeNode(1, null, null)),
            new TreeNode(4, new TreeNode(5, null, null) , new TreeNode(6, null, null))
        );

        System.out.println("树的前序遍历");
        System.out.println(Arrays.toString(preOrderTraverse(root).toArray()));

        System.out.println("树的中序遍历");
        System.out.println(Arrays.toString(midOrderTraverse(root).toArray()));

        System.out.println("树的后序遍历");
        System.out.println(Arrays.toString(postOrderTraverse(root).toArray()));

        System.out.println("树的层序遍历");
        System.out.println(Arrays.toString(sequenceTraverse(root).toArray()));

        System.out.println("求数的最大深度");
        System.out.println(maximumDepth(root));

        System.out.println("检查树是否轴对称");
        TreeNode isAxisymmetricRoot = new TreeNode(
            1,
            new TreeNode(2, new TreeNode(3, null, null) , new TreeNode(4, null, null)),
            new TreeNode(2, new TreeNode(4, null, null) , new TreeNode(3, null, null))
        );
        System.out.println(isAxisymmetric(isAxisymmetricRoot));

        System.out.println("翻转二叉树");
        System.out.println(flipTreeNode(root));
        System.out.println();

        System.out.println("判断树中是否存在根节点到叶子节点的路径之和为特定值的路径");
        System.out.println(existRootEndValTargetSum(root, 0));
        System.out.println(existRootEndValTargetSum(root, 4));
        System.out.println(existRootEndValTargetSum(root, 5));
        System.out.println(existRootEndValTargetSum(root, 12));
        System.out.println(existRootEndValTargetSum(root, 14));
        System.out.println(existRootEndValTargetSum(root, 16));

        System.out.println("获取二叉树指定节点的子树");
        TreeNode getSubTreeRoot = new TreeNode(
            4,
            new TreeNode(2, new TreeNode(1, null, null) , new TreeNode(3, null, null)),
            new TreeNode(7, new TreeNode(6, null, null) , new TreeNode(8, null, null))
        );
        System.out.println(Arrays.toString(sequenceTraverse(getSubTree(getSubTreeRoot, 2)).toArray()));
        System.out.println(Arrays.toString(sequenceTraverse(getSubTree(getSubTreeRoot, 7)).toArray()));

        System.out.println("二叉搜索树中的插入操作");
        TreeNode getInsertedNodeTreeRoot = new TreeNode(
            4,
            new TreeNode(1, new TreeNode(0, null, null) , new TreeNode(3, null, null)),
            new TreeNode(7, null, null)
        );
        System.out.println(Arrays.toString(sequenceTraverse(getInsertedNodeTree(getInsertedNodeTreeRoot, 2)).toArray()));
        System.out.println(Arrays.toString(sequenceTraverse(getInsertedNodeTree(getInsertedNodeTreeRoot, 5)).toArray()));

        System.out.println("验证二叉搜索树");
        System.out.println(judgeValidSearchTree(getInsertedNodeTreeRoot));

        System.out.println("两数之和");
        System.out.println(checkTwoNodeSumEqualTarget(getInsertedNodeTreeRoot, 5));
        System.out.println(checkTwoNodeSumEqualTarget(getInsertedNodeTreeRoot, 8));
        System.out.println(checkTwoNodeSumEqualTarget(getInsertedNodeTreeRoot, 10));
        System.out.println(checkTwoNodeSumEqualTarget(getInsertedNodeTreeRoot, 11));
        System.out.println(checkTwoNodeSumEqualTarget(getInsertedNodeTreeRoot, 18));
        System.out.println(checkTwoNodeSumEqualTarget(getInsertedNodeTreeRoot, 100));

        System.out.println("二叉搜索树的最近公共祖先");// todo
        TreeNode searchTreeCommonAncestorTreeRoot = new TreeNode(
            6,
            new TreeNode(2, new TreeNode(0, null, null) , new TreeNode(4, null, null)),
            new TreeNode(8, new TreeNode(7, null, null) , new TreeNode(9, null, null))
        );
        System.out.println(
                searchTreeCommonAncestor(
                        searchTreeCommonAncestorTreeRoot,
                        new TreeNode(2, new TreeNode(0, null, null) , new TreeNode(4, null, null)),
                        new TreeNode(8, new TreeNode(7, null, null) , new TreeNode(9, null, null))
                )
        );

    }

    /**
     * 买卖股票最佳时机
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     * 示例 1：
     * 输入：[7,1,5,3,6,4]
     * 输出：5
     * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
     * 示例 2：
     * 输入：prices = [7,6,4,3,1]
     * 输出：0
     * 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
     * 1 <= prices.length <= 105
     * 0 <= prices[i] <= 104
     * @param prices
     * @return
     */
    public static int getBiggestProfits(int[] prices){

         /*
        DP思想：
        记录【今天之前买入的最小值】
        计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】
        比较【每天的最大获利】，取最大值即可
        */

        if (prices.length <= 1){
            return 0;
        }

        int min = prices[0];
        int max = 0;
        for(int i = 1; i<prices.length; i++){
            max = Math.max(max, prices[i] - min);
            min = Math.min(min, prices[i]);
        }

        return max;

    }

    /**
     *  两个数组的交集:
     *  给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，
     *  应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
     *
     * 示例 1：
     * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
     * 输出：[2,2]
     * 示例 2:
     * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
     * 输出：[4,9]
     * 提示：
     * 1 <= nums1.length, nums2.length <= 1000
     * 0 <= nums1[i], nums2[i] <= 1000
     *
     * 进阶：
     * 如果给定的数组已经排好序呢？你将如何优化你的算法？
     * 如果 nums1 的大小比 nums2 小，哪种方法更优？
     * 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] getTwoArrayIntersection(int[] nums1, int[] nums2){
        Map<Integer, Integer> resultMap = new HashMap(nums1.length + nums2.length);
        for (int item : nums1) {
            for (int value : nums2) {
                if (item == value) {
                    if (resultMap.containsKey(item)) {
                        resultMap.put(item, resultMap.get(item) + 1);
                    } else {
                        resultMap.put(item, 1);
                    }
                    break;
                }
            }
        }
        List<Integer> resultList = new ArrayList<>();
        for (Entry<Integer, Integer> entry : resultMap.entrySet()) {
            final Integer num = entry.getKey();
            final Integer count = entry.getValue();
            for (int i = 0; i < count; i++) {
                resultList.add(num);
            }
        }
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }

    /**
     * 根据指定的行数生成杨辉三角形状的二维数组
     * @param numRows
     * @return
     */
    public static List<List<Integer>> generateYangHuiTriangle(int numRows) {
        List<List<Integer>> numsList = new ArrayList<>();
        for(int i=0; i<numRows; i++){
            List<Integer> numList = new ArrayList<>();
            numsList.add(numList);
            for(int j=0; j<=i; j++){
                if(j==0 || j==i){
                    numList.add(1);
                } else {
                    numList.add(numsList.get(i-1).get(j-1) + numsList.get(i-1).get(j));
                }
            }
        }
        return numsList;
    }

    /**
     * 给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1 。
     * 示例 1：
     * 输入: s = "leetcode"
     * 输出: 0
     * 示例 2:
     * 输入: s = "loveleetcode"
     * 输出: 2
     * 示例 3:
     * 输入: s = "aabb"
     * 输出: -1
     * @param s
     * @return
     */
    public static int findFirstUniqChar(String s) {
        Map<Character,Integer> map = new LinkedHashMap<>();
        for(int i=0; i<s.length(); i++){
            if (map.containsKey(s.charAt(i))){
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            } else {
                map.put(s.charAt(i), 1);
            }
        }
        for (Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1){
                return s.indexOf(entry.getKey());
            }
        }
        return -1;
    }

    /**
     * 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
     *      * 如果可以，返回 true ；否则返回 false 。
     *      * magazine 中的每个字符只能在 ransomNote 中使用一次。
     *      * 示例 1：
     *      * 输入：ransomNote = "a", magazine = "b"
     *      * 输出：false
     *      * 示例 2：
     *      * 输入：ransomNote = "aa", magazine = "ab"
     *      * 输出：false
     *      * 示例 3：
     *      * 输入：ransomNote = "aa", magazine = "aab"
     *      * 输出：true
     *      * 提示：
     *      * 1 <= ransomNote.length, magazine.length <= 105
     *      * ransomNote 和 magazine 由小写英文字母组成
     * @param ransomNote
     * @param magazine
     * @return
     */
    public static  boolean judgeStringCanBeConstructByOtherStringChar(String ransomNote, String magazine) {
        // 时间复杂度m+n
        //获取字典的字符数量hash表
        Map<Character,Integer> maganizeMap = new HashMap<>();
        for (int i = 0; i <magazine.length() ; i++) {
            char maganizeChar = magazine.charAt(i);
            maganizeMap.put(maganizeChar, maganizeMap.getOrDefault(maganizeChar, 0) + 1);
        }

        //组装要生成的文本
        for(int i=0; i<ransomNote.length(); i++){
            char ransomChar = ransomNote.charAt(i);
            if(!maganizeMap.containsKey(ransomChar)){
                return false;
            } else {
                if(maganizeMap.get(ransomChar) == 0){
                    return false;
                }
                maganizeMap.put(ransomChar, maganizeMap.get(ransomChar) - 1);
            }
        }

        return true;
    }
    public static  boolean judgeStringCanBeConstructByOtherStringChar1(String ransomNote, String magazine) {
        // 时间复杂度m
        StringBuffer sb = new StringBuffer(magazine);
        int index = 0;
        for (char c : ransomNote.toCharArray()) {
            index = sb.indexOf(String.valueOf(c));
            if (index >= 0) {
                sb.deleteCharAt(index);
            } else {
                return false;
            }
        }
        return true;
    }

    /**
     * 矩阵置零
     * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
     * 示例 1：
     * 输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
     * 1    1   1
     * 1    0   1
     * 1    1   1
     * 输出：[[1,0,1],[0,0,0],[1,0,1]]
     * 1    0   1
     * 0    0   0
     * 1    0   1
     * 示例 2：
     * 输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
     * 0    1   2   0
     * 3    4   5   2
     * 1    3   1   5
     * 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
     * 0    0   0   0
     * 0    4   5   0
     * 0    3   1   0
     * 提示：
     * m == matrix.length
     * n == matrix[0].length
     * 1 <= m, n <= 200
     * -231 <= matrix[i][j] <= 231 - 1
     * 进阶：
     * 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
     * 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
     * 你能想出一个仅使用常量空间的解决方案吗？
     * @param nums
     * @return
     */
    public static int[][] getSetZeroMatrix(int[][] nums){

        Set<Integer> rowIndex = new HashSet<>();
        Set<Integer> colomnIndex = new HashSet<>();

        // 查找元素为0的位置 （i，j）
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                if (nums[i][j] == 0){
                    rowIndex.add(i);
                    colomnIndex.add(j);
                }
            }
        }

        // 将矩阵中i行，j列的所有元素置零
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                if (rowIndex.contains(i) || colomnIndex.contains(j)){
                    nums[i][j] = 0;
                }
            }
        }

        return nums;
    }

    /**
     * 有效的字母异位词
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     * 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
     * 示例 1:
     * 输入: s = "anagram", t = "nagaram"
     * 输出: true
     * 示例 2:
     * 输入: s = "rat", t = "car"
     * 输出: false
     * 提示:
     * 1 <= s.length, t.length <= 5 * 104
     * s 和 t 仅包含小写字母
     * @param s
     * @param t
     * @return
     */
    public static boolean judgeTwoStringIsLetterDifferentPositionVocabulary(String s, String t){
        if (s.length() != t.length()){
            return false;
        }
        int[] dic = new int[26];
        for(int i=0; i<s.length(); i++){
            dic[s.charAt(i) - 97]++;
        }
        for(int i=0; i<t.length(); i++){
            dic[t.charAt(i) - 97]--;
        }
        for(int num : dic){
            if (num > 0){
                return false;
            }
        }
        return true;
    }

    /**
     * 环形链表
     *         给你一个链表的头节点 head ，判断链表中是否有环。
     *         如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，
     *         评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     *         如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     *         示例 1：
     *         输入：head = [3,2,0,-4], pos = 1
     *         输出：true
     *         解释：链表中有一个环，其尾部连接到第二个节点。
     *         示例 2：
     *         输入：head = [1,2], pos = 0
     *         输出：true
     *         解释：链表中有一个环，其尾部连接到第一个节点。
     *         示例 3：
     *         输入：head = [1], pos = -1
     *         输出：false
     *         解释：链表中没有环。
     *         提示：链表中节点的数目范围是 [0, 104],-105 <= Node.val <= 105,pos 为 -1 或者链表中的一个 有效索引 。
     *         进阶：你能用 O(1)（即，常量）内存解决此问题吗？
     * @param head
     * @return
     */
    public static boolean judgeLinkedListNodeHaveLoop(ListNode head){
        //方法一：哈希表
        //思路及算法
        //最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。
        //具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，
        // 则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。
        Set<ListNode> set = new HashSet<>();
        while (head != null){
            if (set.contains(head)){
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
        void show(){
            ListNode node = this;
            System.out.print("链表" + ":");
            while (node.next != null){
                System.out.print(node.val + "->");
                node = node.next;
            }
            System.out.println(node.val);
        }
    }
    public static boolean judgeLinkedListNodeHaveLoop1(ListNode head){
        // 方法二：快慢指针
        //思路及算法
        //本方法需要读者对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。
        //我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。
        // 初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表
        // 否则快指针将到达链表尾部，该链表不为环形链表。
        if (head == null || head.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast){
            if (fast == null || fast.next == null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    /**
     * 合并两个有序链表
     *         将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     *         示例 1：
     *         输入：l1 = [1,2,4], l2 = [1,3,4]
     *         输出：[1,1,2,3,4,4]
     *         示例 2：
     *         输入：l1 = [], l2 = []
     *         输出：[]
     *         示例 3：
     *         输入：l1 = [], l2 = [0]
     *         输出：[0]
     *         提示：两个链表的节点数目范围是 [0, 50]
     *         -100 <= Node.val <= 100
     *         l1 和 l2 均按 非递减顺序 排列
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoSortedLinkedList(ListNode list1, ListNode list2){

        // 方法一：递归
        //我们直接将以上递归过程建模，同时需要考虑边界情况。
        //如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。
        // 否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        if (list1.val < list2.val){
            list1.next = mergeTwoSortedLinkedList(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoSortedLinkedList(list1, list2.next);
            return list2;
        }
    }
    public static ListNode mergeTwoSortedLinkedList2(ListNode list1, ListNode list2){

        //方法二：迭代
        //  我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，
        //将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。
        //  首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，
        //我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前节点的值小于等于 l2 ，
        //我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则，我们对 l2 做同样的操作。
        //不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。
        //  在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，
        //它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list2;
        }

        return list1;
    }

    /**
     * 移除链表元素
     * 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
     * 示例 1：
     * 输入：head = [1,2,6,3,4,5,6], val = 6
     * 输出：[1,2,3,4,5]
     * 示例 2：
     * 输入：head = [], val = 1
     * 输出：[]
     * 示例 3：
     * 输入：head = [7,7,7,7], val = 7
     * 输出：[]
     * 提示：
     * 列表中的节点数目在范围 [0, 104] 内
     * 1 <= Node.val <= 50
     * 0 <= val <= 50
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElements(ListNode head, int val) {
        //方法一：递归
        //链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点，可以用递归实现。
        //对于给定的链表，首先对除了头节点 {head}head 以外的节点进行删除操作，然后判断 {head}head 的节点值是否等于给定的 {val}val。
        // 如果 {head}head 的节点值等于 {val}val，则 {head}head 需要被删除，因此删除操作后的头节点为 {head}.{next}head.next；如果 {head}head 的节点值不等于 {val}val，则 {head}head 保留，因此删除操作后的头节点还是 {head}head。上述过程是一个递归的过程。
        //递归的终止条件是 {head}head 为空，此时直接返回 {head}head。当 {head}head 不为空时，递归地进行删除操作，
        // 然后判断 {head}head 的节点值是否等于 {val}val 并决定是否要删除 {head}head。
        if (head == null){
            return head;
        }

        head.next = removeElements(head.next, val);
        return head.val == val ? head.next: head;
    }
    public static ListNode removeElements1(ListNode head, int val) {
        // 方法二：迭代
        //也可以用迭代的方法删除链表中所有节点值等于特定值的节点。
        //用 {temp}temp 表示当前节点。如果 {temp}temp 的下一个节点不为空且下一个节点的节点值等于给定的 {val}val，则需要删除下一个节点。删除下一个节点可以通过以下做法实现：
        //{temp}.{next} = {temp}.{next}.{next}
        //temp.next=temp.next.next
        //如果 {temp}temp 的下一个节点的节点值不等于给定的 {val}val，则保留下一个节点，将 {temp}temp 移动到下一个节点即可。
        //当 {temp}temp 的下一个节点为空时，链表遍历结束，此时所有节点值等于 {val}val 的节点都被删除。
        //具体实现方面，由于链表的头节点 {head}head 有可能需要被删除，因此创建哑节点 {dummyHead}dummyHead，
        // 令 {dummyHead}.{next} = {head}dummyHead.next=head，初始化 {temp}={dummyHead}temp=dummyHead，然后遍历链表进行删除操作。
        // 最终返回 {dummyHead}.{next}dummyHead.next 即为删除操作后的头节点。
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }

    /**
     * 反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * 示例 1：
     * 输入：head = [1,2,3,4,5]
     * 输出：[5,4,3,2,1]
     * 示例 2：
     * 输入：head = [1,2]
     * 输出：[2,1]
     * 示例 3：
     * 输入：head = []
     * 输出：[]
     * 提示：
     * 链表中节点的数目范围是 [0, 5000]
     * -5000 <= Node.val <= 5000
     * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
     * @param head
     * @return
     */
    public static ListNode reverseListNode(ListNode head) {
        // 迭代
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head, second = head.next;
        first.next = null;
        while (second != null) {
            ListNode temp = second.next;
            second.next = first;
            first = second;
            second = temp;
        }
        return first;
    }
    /*
       1->2->3->4->5
    n<-1  2->3->4->5
    n<-1<-2  3->4->5
    n<-1<-2<-3  4->5
    n<-1<-2<-3<-4  5
    n<-1<-2<-3<-4<-5
     */
    public static ListNode reverseListNode1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseListNode1(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    /**
     * 删除排序链表中的重复元素
     * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表 。
     * 示例 1：
     * 输入：head = [1,1,2]
     * 输出：[1,2]
     * 示例 2：
     * 输入：head = [1,1,2,3,3]
     * 输出：[1,2,3]
     * 提示：
     * 链表中节点数目在范围 [0, 300] 内
     * -100 <= Node.val <= 100
     * 题目数据保证链表已经按升序 排列
     * @param head
     * @return
     */
    public static ListNode deleteListNodeDuplicateElements(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }

        Set<Integer> nums = new HashSet<>();
        ListNode previousNode = head;
        ListNode temp = head.next;
        nums.add(head.val);

        while (temp != null){
            if (!nums.add(temp.val)){
                previousNode.next = temp.next;
            } else {
                previousNode = temp;
            }
            temp = temp.next;
        }

        return head;
    }

    /**
     * 有效的括号
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 示例 1：
     * 输入：s = "()"
     * 输出：true
     * 示例 2：
     * 输入：s = "()[]{}"
     * 输出：true
     * 示例 3：
     * 输入：s = "(]"
     * 输出：false
     * 示例 4：
     * 输入：s = "([)]"
     * 输出：false
     * 示例 5：
     * 输入：s = "{[]}"
     * 输出：true
     * 提示：
     * 1 <= s.length <= 104
     * s 仅由括号 '()[]{}' 组成
     * @param s
     * @return boolean
     */
    public static boolean judgeValidBracket(String s) {
        if (s.length()%2 == 1){
            return false;
        }

        int n = s.length();
        Map<Character,Character> charMap = new HashMap<>();
        charMap.put(')','(');
        charMap.put(']','[');
        charMap.put('}','{');
        Stack<Character> stack = new Stack<>();

        for(int i=0; i<n; i++){
            char c = s.charAt(i);
            if (charMap.containsKey(c)){
                if (stack.isEmpty() || stack.peek() != charMap.get(c)){
                    return false;
                }
                stack.pop();
            } else{
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

    //用栈实现队列
    //请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
    //实现 MyQueue 类：
    //void push(int x) 将元素 x 推到队列的末尾
    //int pop() 从队列的开头移除并返回元素
    //int peek() 返回队列开头的元素
    //boolean empty() 如果队列为空，返回 true ；否则，返回 false
    //说明：
    //你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    //你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
    //示例 1：
    //输入：
    //["MyQueue", "push", "push", "peek", "pop", "empty"]
    //[[], [1], [2], [], [], []]
    //输出：
    //[null, null, null, 1, 1, false]
    //进阶：
    //你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
    static class MyQueue {
        private Stack<Integer> inStack = new Stack<>();
        private Stack<Integer> outStack = new Stack<>();

        public MyQueue() {}

        //
        // 3 2 1
        public void push(Integer x) {
            inStack.push(x);
        }

        public Integer pop() {
            if (outStack.empty()){
                in2Out();
            }
            return outStack.pop();
        }

        public Integer peek() {
            if (outStack.empty()){
                in2Out();
            }
            return outStack.peek();
        }

        public Boolean empty() {
            return inStack.empty() && outStack.empty();
        }

        private void in2Out(){
            if (outStack.empty()){
                while (!inStack.empty()){
                    outStack.push(inStack.pop());
                }
            }
        }
    }

    /**
     * 树节点类
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /*
    二叉树遍历
          3
       2    4
    0  1  5   6
    前 3201456
    中 0213546
    后 3465210
     */

    /**
     * 给你二叉树的根节点 root ，返回它节点值的前序遍历。
     * 示例 1：
     * 输入：root = [1,null,2,3]
     * 输出：[1,2,3]
     * 示例 2：
     * 输入：root = []
     * 输出：[]
     * 示例 3：
     * 输入：root = [1]
     * 输出：[1]
     * 示例 4：
     * 输入：root = [1,2]
     * 输出：[1,2]
     * 示例 5：
     * 输入：root = [1,null,2]
     * 输出：[1,2]
     * 提示：
     * 树中节点数目在范围 [0, 100] 内
     * -100 <= Node.val <= 100
     * 进阶：递归算法很简单，你可以通过迭代算法完成吗？
     * @param treeNode
     * @return
     */
    public static List<Integer> preOrderTraverse(TreeNode treeNode) {
        // 前 3201456
        List<Integer> result = new ArrayList<>();
        preOrderTraverseRecursive(treeNode, result);
        return result;
    }
    public static void preOrderTraverseRecursive(TreeNode treeNode, List<Integer> result) {
        if (treeNode==null || result==null){
            return;
        }
        result.add(treeNode.val);

        if (treeNode.left != null){
            preOrderTraverseRecursive(treeNode.left, result);
        }

        if (treeNode.right != null){
            preOrderTraverseRecursive(treeNode.right, result);
        }
    }

    /**
     * 二叉树的中序遍历
     * 给定一个二叉树的根节点 root ，返回它的中序遍历 。
     * 示例 1：
     * 输入：root = [1,null,2,3]
     * 输出：[1,3,2]
     * 示例 2：
     * 输入：root = []
     * 输出：[]
     * 示例 3：
     * 输入：root = [1]
     * 输出：[1]
     * 提示：
     *     树中节点数目在范围 [0, 100] 内
     *     -100 <= Node.val <= 100
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * @param treeNode
     */
    public static List<Integer> midOrderTraverse(TreeNode treeNode) {
        //       3
        //   2    4
        //0  1  5   6
        // 中 0213546
        List<Integer> result = new ArrayList<>();
        midOrderTraverseRecursive(treeNode, result);
        return result;
    }
    public static void midOrderTraverseRecursive(TreeNode treeNode, List<Integer> result) {
        if (treeNode==null){
            return;
        }

        if (treeNode.left != null){
            midOrderTraverseRecursive(treeNode.left, result);
        }

        result.add(treeNode.val);

        if (treeNode.right != null){
            midOrderTraverseRecursive(treeNode.right, result);
        }
    }

    /**
     * 二叉树的后序遍历
     * 给你一棵二叉树的根节点 root ，返回其节点值的后序遍历 。
     * 示例 1：
     * 输入：root = [1,null,2,3]
     * 输出：[3,2,1]
     * 示例 2：
     * 输入：root = []
     * 输出：[]
     * 示例 3：
     * 输入：root = [1]
     * 输出：[1]
     * 提示：
     *     树中节点的数目在范围 [0, 100] 内
     *     -100 <= Node.val <= 100
     * @param treeNode
     */
    public static List<Integer> postOrderTraverse(TreeNode treeNode) {
        //       3
        //   2    4
        //0  1  5   6
        // 后 0125643
        List<Integer> result = new ArrayList<>();
        postOrderTraverseRecursive(treeNode, result);
        return result;
    }
    public static void postOrderTraverseRecursive(TreeNode treeNode, List<Integer> result) {

        if (treeNode==null){
            return;
        }

        if (treeNode.left != null){
            postOrderTraverseRecursive(treeNode.left, result);
        }

        if (treeNode.right != null){
            postOrderTraverseRecursive(treeNode.right, result);
        }

        result.add(treeNode.val);
    }

    /**
     * 二叉树的层序遍历
     * 给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。
     * 示例 1：
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：[[3],[9,20],[15,7]]
     * 示例 2：
     * 输入：root = [1]
     * 输出：[[1]]
     * 示例 3：
     * 输入：root = []
     * 输出：[]
     * 提示：
     *     树中节点数目在范围 [0, 2000] 内
     *     -1000 <= Node.val <= 1000
     * @param treeNode
     */
    public static List<Integer> sequenceTraverse(TreeNode treeNode) {
        //       3
        //   2    4
        //0  1  5   6
        // 层序 3240156

        List<Integer> result = new ArrayList<>();
        List<TreeNode> treeNodes = new ArrayList<>();
        List<TreeNode> nextTreeNodes;
        treeNodes.add(treeNode);

        while (treeNodes.size() > 0){
            nextTreeNodes = new ArrayList<>();

            for (TreeNode node : treeNodes) {

                if (node == null){
                    continue;
                }

                result.add(node.val);

                if (node.left != null){
                    nextTreeNodes.add(node.left);
                }

                if (node.right != null){
                    nextTreeNodes.add(node.right);
                }
            }
            treeNodes = nextTreeNodes;
        }
        return result;
    }

    /**
     * 二叉树的最大深度
     * 给定一个二叉树，找出其最大深度。
     * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     * 说明: 叶子节点是指没有子节点的节点。
     * 示例：
     * 给定二叉树 [3,9,20,null,null,15,7]，
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回它的最大深度 3 。
     * @param treeNode
     * @return
     */
    public static int maximumDepth(TreeNode treeNode) {

        // 通过层序遍历的次数来获取最大深度

        int depth = 0;
        List<TreeNode> treeNodes = new ArrayList<>();
        List<TreeNode> nextTreeNodes;
        treeNodes.add(treeNode);

        while (treeNodes.size() > 0){
            nextTreeNodes = new ArrayList<>();

            for (TreeNode node : treeNodes) {

                if (node == null){
                    continue;
                }

                if (node.left != null){
                    nextTreeNodes.add(node.left);
                }

                if (node.right != null){
                    nextTreeNodes.add(node.right);
                }
            }
            depth++;
            treeNodes = nextTreeNodes;
        }
        return depth;
    }

    /**
     * 对称二叉树
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     * 示例 1：
     * 输入：root = [1,2,2,3,4,4,3]
     * 输出：true
     * 示例 2：
     * 输入：root = [1,2,2,null,3,null,3]
     * 输出：false
     * 提示：
     *     树中节点数目在范围 [1, 1000] 内
     *     -100 <= Node.val <= 100
     * @param treeNode
     * @return
     */
    public static boolean isAxisymmetric(TreeNode treeNode) {
        //        1
        //       / \
        //      2   2
        //     /\  /\
        //    3 4 4  3
        List<Integer> leftList = null;
        List<Integer> rightList = null;
        if (treeNode.right==null && treeNode.left==null){
            return true;
        }

        if (treeNode.left!=null){
            leftList = sequenceTraverse(treeNode.left);
        }
        if (treeNode.right!=null){
            rightList = sequenceTraverseForAxisymmetric(treeNode.right);
        }

        if (leftList == null || rightList == null){
            return false;
        }

        for (int i = 0; i < leftList.size(); i++) {
            if (! leftList.get(i).equals(rightList.get(i))){
                return false;
            }
        }

        return true;
    }
    public static List<Integer> sequenceTraverseForAxisymmetric(TreeNode treeNode) {
        List<Integer> result = new ArrayList<>();
        List<TreeNode> treeNodes = new ArrayList<>();
        List<TreeNode> nextTreeNodes;
        treeNodes.add(treeNode);

        while (treeNodes.size() > 0){
            nextTreeNodes = new ArrayList<>();

            for (TreeNode node : treeNodes) {

                if (node == null){
                    continue;
                }

                result.add(node.val);

                if (node.right != null){
                    nextTreeNodes.add(node.right);
                }

                if (node.left != null){
                    nextTreeNodes.add(node.left);
                }

            }
            treeNodes = nextTreeNodes;
        }
        return result;
    }

    /**
     * 翻转二叉树
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     * 示例 1：
     * 输入：root = [4,2,7,1,3,6,9]
     * 输出：[4,7,2,9,6,3,1]
     * 示例 2：
     * 输入：root = [2,1,3]
     * 输出：[2,3,1]
     * 示例 3：
     * 输入：root = []
     * 输出：[]
     * 提示：
     * 树中节点数目范围在 [0, 100] 内,-100 <= Node.val <= 100
     * @param treeNode
     * @return
     */
    public static TreeNode flipTreeNode(TreeNode treeNode) {

        //       3                3
        //   2    4            4    2
        //0  1  5   6        6  5  1  0
        if (treeNode == null){
            return treeNode;
        }

        flipTreeNodeRecursive(treeNode);
        return treeNode;
    }
    public static void flipTreeNodeRecursive(TreeNode treeNode) {
        if (treeNode == null){
            return;
        }

        TreeNode temp = treeNode.right;
        treeNode.right = treeNode.left;
        treeNode.left = temp;

        flipTreeNodeRecursive(treeNode.left);
        flipTreeNodeRecursive(treeNode.right);
    }

    /**
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点
     * 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回true ；否则，返回false 。
     * 叶子节点是指没有子节点的节点。
     * 示例 1：
     * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
     * 输出：true
     * 解释：等于目标和的根节点到叶节点路径如上图所示。
     * 示例 2：
     * 输入：root = [1,2,3], targetSum = 5
     * 输出：false
     * 解释：树中存在两条根节点到叶子节点的路径：
     * (1 --> 2): 和为 3
     * (1 --> 3): 和为 4
     * 不存在 sum = 5 的根节点到叶子节点的路径。
     * 示例 3：
     * 输入：root = [], targetSum = 0
     * 输出：false
     * 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
     * 提示：
     * 树中节点的数目在范围 [0, 5000] 内
     * -1000 <= Node.val <= 1000
     * -1000 <= targetSum <= 1000
     * @param treeNode
     * @return
     */
    public static boolean existRootEndValTargetSum(TreeNode treeNode, int targetSum) {
        //       3
        //   2    4
        //0  1  5   6
        //0 4 5 12 14
        if (treeNode==null){
            return false;
        }

        if (treeNode.left==null && treeNode.right==null && treeNode.val==targetSum){
            return true;
        }

        Map<TreeNode, Integer> treeNodeSumMap = new HashMap<>();
        treeNodeSumMap.put(treeNode, treeNode.val);
        preOrderTraverseRecursive(treeNode, treeNodeSumMap, treeNode.val);

        for (Integer value : treeNodeSumMap.values()) {
            if (value==targetSum){
                return true;
            }
        }

        return false;
    }
    public static void preOrderTraverseRecursive(TreeNode treeNode, Map<TreeNode, Integer> treeNodeSumMap, int sum) {

        if (treeNode.left != null){
            treeNodeSumMap.put(treeNode.left, sum + treeNode.left.val);
            treeNodeSumMap.remove(treeNode);
            preOrderTraverseRecursive(treeNode.left, treeNodeSumMap, treeNodeSumMap.get(treeNode.left));
        }

        if (treeNode.right != null){
            treeNodeSumMap.put(treeNode.right, sum + treeNode.right.val);
            treeNodeSumMap.remove(treeNode);
            preOrderTraverseRecursive(treeNode.right,  treeNodeSumMap, treeNodeSumMap.get(treeNode.right));
        }
    }

    /**
     * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
     * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
     * 示例 1:
     * 输入：root = [4,2,7,1,3], val = 2
     * 输出：[2,1,3]
     * 示例 2:
     * 输入：root = [4,2,7,1,3], val = 5
     * 输出：[]
     * 提示：
     * 数中节点数在 [1, 5000] 范围内
     * 1 <= Node.val <= 107
     * root 是二叉搜索树
     * 1 <= val <= 107
     * @param root
     * @param val
     * @return
     */
    public static TreeNode getSubTree(TreeNode root, int val){
        // 递归
        // if (root==null){
        //     return null;
        // }
        // if (root.val==val){
        //     return root;
        // }
        // return searchBST(root.val > val ? root.left : root.right, val);

        // 迭代
        while(root!=null){
            if (root.val==val){
                return root;
            }
            root = root.val>val ? root.left : root.right;
        }
        return null;
    }

    /**
     * 二叉搜索树中的插入操作
     * 给定二叉搜索树（BST）的根节点root和要插入树中的值value，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。
     * 输入数据保证新值和原始二叉搜索树中的任意节点值都不同。
     * 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。
     * 示例 1：
     * 输入：root = [4,2,7,1,3], val = 5
     * 输出：[4,2,7,1,3,5]
     * 解释：另一个满足题目要求可以通过的树是：
     * 示例 2：
     * 输入：root = [40,20,60,10,30,50,70], val = 25
     * 输出：[40,20,60,10,30,50,70,null,null,25]
     * 示例 3：
     * 输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
     * 输出：[4,2,7,1,3,5]
     * 提示：
     * 树中的节点数将在 [0, 104]的范围内。
     * -108 <= Node.val <= 108
     * 所有值 Node.val 是 独一无二 的。
     * -108 <= val <= 108
     * 保证 val 在原始BST中不存在。
     * @param root
     * @param val
     * @return
     */
    public static TreeNode getInsertedNodeTree(TreeNode root, int val){
        //首先回顾二叉搜索树的性质：对于任意节点root 而言，左子树（如果存在）上所有节点的值
        //均小于root.val，右子树（如果存在）上所有节点的值均大于root.val，且它们都是二叉搜索树。
        //因此，当将val 插入到以root 为根的子树上时，根据val与root.val 的大小关系，就可以确定要将val 插入到哪个子树中。
        //如果该子树不为空，则问题转化成了将val 插入到对应子树上.
        //否则，在此处新建一个以val 为值的节点，并链接到其父节点root 上。

        if (root==null){
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while(pos!=null){
            if (pos.val < val){
                if (pos.right==null){
                    pos.right = new TreeNode(val);
                    break;
                } else{
                    pos = pos.right;
                }
            }
            if (pos.val > val){
                if (pos.left==null){
                    pos.left = new TreeNode(val);
                    break;
                } else{
                    pos = pos.left;
                }
            }
        }
        return root;
    }

    /**
     * 验证二叉搜索树
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     * 有效二叉搜索树定义如下：
     * 节点的左子树只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     * 示例 1：
     * 输入：root = [2,1,3]
     * 输出：true
     * 示例 2：
     * 输入：root = [5,1,4,null,null,3,6]
     * 输出：false
     * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
     * 提示：
     * 树中节点数目范围在[1, 104] 内
     * -231 <= Node.val <= 231 - 1
     * @param root
     * @return
     */
    public static boolean judgeValidSearchTree(TreeNode root) {
        return isValidTree(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private static boolean isValidTree(TreeNode root, long lower, long higher){
        if (root==null){
            return true;
        }

        if (root.val <= lower || root.val >= higher){
            return false;
        }

        return isValidTree(root.left, lower, root.val) && isValidTree(root.right, root.val, higher);
    }

    /**
     * 两数之和 IV - 输入二叉搜索树
     * 给定一个二叉搜索树root和一个目标结果 k，
     * 如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回true。
     * 示例 1：
     * 输入: root = [5,3,6,2,4,null,7], k = 9
     * 输出: true
     * 示例 2：
     * 输入: root = [5,3,6,2,4,null,7], k = 28
     * 输出: false
     * 提示:
     * 二叉树的节点个数的范围是  [1, 104].
     * -104 <= Node.val <= 104
     * 题目数据保证，输入的 root是一棵有效的二叉搜索树
     * -105 <= k <= 105
     * @param root
     * @param k
     * @return
     */
    public static boolean checkTwoNodeSumEqualTarget(TreeNode root, int k){
        Map<Integer,Integer> nums = new HashMap<>();
        return preOrderTraverseRecursive1(root, nums, k);
    }
    public static boolean preOrderTraverseRecursive1(TreeNode root, Map<Integer,Integer> nums, int k) {
        if (root!=null){
            if (nums.containsKey(root.val)){
                return true;
            } else {
                nums.put(k - root.val, root.val);
            }

            if (root.left != null){
                if (preOrderTraverseRecursive1(root.left, nums, k)){
                    return true;
                }
            }

            if (root.right != null){
                if (preOrderTraverseRecursive1(root.right, nums, k)){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 二叉搜索树的最近公共祖先:给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
     * 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
     * 示例 1:
     * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
     * 输出: 6
     * 解释: 节点 2 和节点 8 的最近公共祖先是 6。
     * 示例 2:
     * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
     * 输出: 2
     * 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
     * 说明:
     * 所有节点的值都是唯一的。
     * p、q 为不同节点且均存在于给定的二叉搜索树中。
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode searchTreeCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        //          6
        //      2      8
        //   0   4   7   9
        // n n  3 5
        //2,8 => 6
        //2,4 => 2
        //0,4 => 2
        // 二叉搜索树
        // 深度尽可能大
        // 所有节点的值都是唯一的
        // p、q 为不同节点且均存在于给定的二叉搜索树中。

        // 个人思路
        // 1、遍历树，获取当前的节点值
        // 2、当前节点值和两个节点的值比较，如果当前节点的值在给定的两个数值的闭区间内，
        // 则该节点为一个公共父节点，但是不一定为深度最大的父节点，将节点和对应的深度存储
        // 3、遍历完成，找出深度最大的节点

        // 官方思路
        // 从根节点开始，逐个遍历每个节点，如果节点的值大于p和q的值，那么公共节点一定在该节点的左节点或左节点的子节点，
        // 如果节点的值小于p和q的值，那么公共节点一定在该节点的右节点或者右节点的子节点，
        // 否则公共节点在该节点或者该节点的子树的节点
        TreeNode ancestor = root;
        while(true){
            if (p.val > ancestor.val && q.val > ancestor.val){
                ancestor = ancestor.right;
            } else if (p.val < ancestor.val && q.val < ancestor.val){
                ancestor = ancestor.left;
            } else {
                break;
            }
        }
        return ancestor;
    }

}
